package com.zgkxzx.数据结构.堆;

/**
 * 创建者   zgkxzx
 * 创建日期 2018/5/9.
 * 功能描述 堆的实现
 */
public class Heap {
    private final static int MAX_SIZE = 30;
    private Node[] heapArray;

    private int currentIndex;

    public Heap() {
        heapArray = new Node[MAX_SIZE];
        currentIndex = 0;
    }


    //插入
    //不用管左右子节点的大小关系，只需要都小于顶点就可
    public boolean insert(int key) {
        if (currentIndex == MAX_SIZE)
            return false;
        heapArray[currentIndex] = new Node(key);
        tickUp(currentIndex);
        currentIndex++;

        return true;
    }

    //向上转型
    private void tickUp(int index) {
        Node node = heapArray[index];
        int parentIndex = (index - 1) / 2;
        //如果检索大于零
        //存在父节点
        //子节点的关健值大于父节点的关健值
        //这时要交换位置
        while (index > 0 && heapArray[index].key > heapArray[parentIndex].key) {
            Node tmp = heapArray[index];
            heapArray[index] = heapArray[parentIndex];
             heapArray[parentIndex] = tmp;
            index = parentIndex;
            parentIndex = (index - 1) / 2;
        }
        //heapArray[index] = node;
    }

    //删除
    public void delete() {
        Node root = heapArray[0];
        heapArray[0] = heapArray[--currentIndex];
        tickDown(0);
    }
    //向下调整
    //从更节点找它的子节点，然后比较，进行置换
    private void tickDown(int i) {

    }

    //遍历
    public void display() {
        System.out.println("数组显示");
        for (int i = 0; i < MAX_SIZE; i++) {
            if (heapArray[i] != null) {
//因为没有洞，堆是一颗完全二叉树，所以不用判断这个位置上的结点是否有值，直接显示即可
                System.out.print(heapArray[i].key + " ");
            } else
                System.out.print(" ");
        }
        System.out.println();
        String dot = ".......................................";
        System.out.println(dot + dot);
        int nBlanks = 32;//空格的长度
        int itemsPerRow = 1;//一行
        int column = 0;//一行中的第一个元素
        int j = 0;    //堆中元素的下标
        //当堆中有元素时
        while (currentIndex > 0) {
            if (column == 0)                  // 一行中的第一个元素
                for (int k = 0; k < nBlanks; k++)  //前面的空白
                    System.out.print(' ');
            System.out.print(heapArray[j].key);//输出堆中的元素

            if (++j == currentIndex) //如果堆中元素输出完毕，结束
                break;
            if (++column == itemsPerRow)        // 一行结束
            {
                nBlanks /= 2;                 // 一半的 空格
                itemsPerRow *= 2;             // 两倍的项数
                column = 0;                   // 从新开始
                System.out.println();         //  新的一行
            } else
                for (int k = 0; k < nBlanks * 2 - 2; k++)
                    System.out.print(' ');     // 中间的空格
        }//while循环结束，即堆中元素输出完毕
        System.out.println("\n" + dot + dot);
    }

    //判断是否为空
    public boolean isEmpty() {
        return currentIndex == 0;
    }

    //判断是否为满
    public boolean isFull() {
        return currentIndex == MAX_SIZE;
    }

    private static class Node {
        public int key;
        public Node leftNode;
        public Node rightNode;

        public Node(int key) {
            this.key = key;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "key=" + key +
                    '}';
        }
    }
}
